/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-04-25
 * Time: 14:22
 */

class Node{
    public int value;
    public Node next;

    public Node(int Data){
        this.value = Data;
    }

    public Node removeLastKthNode(Node head,int k) {
        if(head==null||k<1) {
            return head;
        }
        //定义一个当前的节点
        Node cur = head;
        //先让cur走k步，然后对k进行判断
        while(cur!=null) {
            --k;
            cur = cur.next;
        }
        //对k进行判断
        if(k>0) {
            return head;
        }
        if(k==0) {//证明第一个节点就是要删除的节点
            head = head.next;
        }
        if(k<0) {
            //让cur从头开始走然后k++
            cur =head;
            while(++k!=0&&cur!=null) {
                cur = cur.next;
            }
            //此时cur就是要删除节点的前一个节点
            cur.next = cur.next.next;
        }
        return head;
    }


    public Node removeLastKthNode1(Node head,int lastKth) {
        if(head==null||lastKth<1) {
            return head;
        }
        Node cur = head;
        while(cur!=null) {
            lastKth--;
            cur = cur.next;
        }
        if(lastKth>0) {
            return head;
        }
        if(lastKth==0) {
            head= head.next;
        }
        if(lastKth<0) {
            cur =head;
            while(++lastKth!=0) {
                cur =cur.next;
            }
            cur.next = cur.next.next;
        }

        return head;
    }

    public void linkedListDisplay(Node head) {
        Node cur = head;
        while(cur!=null) {
            System.out.print(cur.value+" ");
            cur =cur.next;
        }
        System.out.println();
    }
     //删除链表的中间节点
    public Node removeMidNode(Node head) {
        if(head==null||head.next==null) {//没有节点或者就一个节点没有中间节点不需要删除
            return head;
        }
        if(head.next.next==null) {
            return head.next;
        }
       //使用快慢指针法
        Node slow = head;
        Node fast = head.next;
        Node slowPrev = null;
        while(fast!=null&&fast.next!=null) {
            slowPrev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //此时slow节点就是要删除的节点
        slowPrev.next = slow.next;
        return head;
    }
}

public class TestDemo {

    public static void main(String[] args) {
        Node node = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.next =node2;
        node2.next =null;
//        node2.next =node3;
//        node3.next=null;
//        node3.next =node4;
//        node4.next=node5;
//        node5.next=null;
//        node5.next = node6;
//        node6.next=null;
        node.linkedListDisplay(node1);
        node1.removeMidNode(node1);
        node.linkedListDisplay(node1);



//        node.linkedListDisplay(node1);
//        System.out.println("=================");
//        node.removeLastKthNode(node1,6);
//        node.linkedListDisplay(node1);
//        node.removeLastKthNode(node1,5);
//        node.linkedListDisplay(node1);
//        node.removeLastKthNode(node1,4);
//        node.linkedListDisplay(node1);
//        node.removeLastKthNode(node1,3);
//        node.linkedListDisplay(node1);
//        node.removeLastKthNode(node1,2);
//        node.linkedListDisplay(node1);
//        node.removeLastKthNode(node1,1);
//        node.linkedListDisplay(node1);
//        node.removeLastKthNode(node1,0);
//        node.linkedListDisplay(node1);

    }

}
